package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;

public class Day25_1 {

    public static void main(String[] args) {
        int[]arr=new int[]{2,1,5,3,4,7,0,0};
        heapSort(arr);
        ArrayUtils.print(arr);
    }
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //让每一个数尽可能的向上堆的最上面移动==>堆顶是最大值  ===>1
        for (int index = 0; index < arr.length; index++) {
            heapInsert(arr, index);
        }
//        //1 可以替换为,从倒第二层开始进行堆结构构造
//        ，倒第三层只需要向下一层（倒第二层已经大根堆了） 倒第一层不需要因为没有子节点
//        for (int index = arr.length-1; index > 0; index--) {
//            heapRestructure(arr,index,arr.length);
//        }
        //当前堆大小等于数组长度.小于这个长度的数算作堆中的数
        int heapSize = arr.length;
        //0位置（最大的数） 和heapSize-1交换（最小的数）
        ArrayUtils.swap(arr, 0, heapSize - 1);
        //堆大小减1 代表最大的数不属于堆==> 最大的数已经到了它应该在的位置
        heapSize--;
        //堆大小大于0 代表还有数被移动应该的位置
        while (heapSize > 0) {
            heapRestructure(arr,0,heapSize);
            //0位置（最大的数） 和heapSize-1交换（最小的数）
            ArrayUtils.swap(arr, 0, heapSize - 1);
            //堆大小减1 代表最大的数不属于堆==> 最大的数已经到了它应该在的位置
            heapSize--;
        }
    }

    public static void heapInsert(int[] arr, int index) {
        //如果当前的位置节点大于父节点值，和父节点进行交换，周而复始直到不大于父节点的值
        //0位置的父节点是自己 所有不会进入循环
        while (arr[index] > arr[(index - 1) / 2]) {
            int fatherIndex = (index - 1) / 2;
            ArrayUtils.swap(arr, index, fatherIndex);
            index = fatherIndex;
        }
    }

    public static void heapRestructure(int[] arr, int from, int heapSize) {
        //左右儿子节点的值，如果不存在返回int 最小值
        int left = getValueIfNotExistReturnIntMin(arr, from * 2 + 1, heapSize);
        int right = getValueIfNotExistReturnIntMin(arr, from * 2 + 2, heapSize);
        while (arr[from] < left || arr[from] < right) {
            //左右儿子中较大的
            int tempIndex = left > right ? from * 2 + 1 : from * 2 + 2;
            //交换当前和儿子中较大者
            ArrayUtils.swap(arr, tempIndex, from);
            //刷新状态准备下一轮
            from = tempIndex;
            left = getValueIfNotExistReturnIntMin(arr, from * 2 + 1, heapSize);
            right = getValueIfNotExistReturnIntMin(arr, from * 2 + 2, heapSize);
        }
    }

    public static int getValueIfNotExistReturnIntMin(int[] arr, int index, int heapSize) {
        if (index >= heapSize || index < 0) {
            return Integer.MIN_VALUE;
        }
        return arr[index];
    }
}
